/*
 * @lc app=leetcode.cn id=720 lang=cpp
 *
 * [720] 词典中最长的单词
 */
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <cmath>

using namespace std;\
// @lc code=start
//字典树
class Trie {
private:
    bool isEnd;
    Trie* next[26];
public:
    Trie() {
       this->isEnd = false;
        memset(this->next,0,sizeof(this->next));
    }
    void insert(string word) {
        Trie* node = this;
        for(char c: word) {
            if(node->next[c - 'a'] == nullptr) {
                node->next[c - 'a'] = new Trie();
            }
            node = node->next[c - 'a'];
        }
        node->isEnd = true;
    }
    bool search(string word) {
        Trie* node = this;
        for(char c: word) {
            node = node->next[c - 'a'];
            //如果不存在后续节点或该节点没有对应字符串则返回false
            if(node == nullptr || node->isEnd == false) {
                return false;
            }
        }
        return node->isEnd;
    }
    bool startsWith(string prefix) {
        Trie* node = this;
        for (char c : prefix) {
            node = node->next[c-'a'];
            if (node == NULL) {
                return false;
            }
        }
        return true;
    }
};

class Solution {
private:
    
public:
    string longestWord(vector<string>& words) {
        Trie trie;
        for (const auto & word : words) {
            trie.insert(word);
        }
        string longest = "";
        for (const auto & word : words) {
            if (trie.search(word)) {
                if (word.size() > longest.size() || (word.size() == longest.size() && word < longest)) {
                    longest = word;
                }
            }
        }
        return longest;
    }
};
// @lc code=end

//模拟法
// sort(words.begin(), words.end(), [](const string & a, const string & b) {
//     if (a.size() != b.size()) {
//         return a.size() < b.size();
//     } else {
//         return a > b;
//     }
// });
// string longest = "";
// unordered_set<string> cnt;
// cnt.emplace("");
// for (auto & word : words) {
//     //一开始是空串，每一次如果该字符串-1在cnt中找到，就添加到其中
//     if (cnt.count(word.substr(0, word.size() - 1))) {
//         cnt.emplace(word);
//         longest = word;
//     }
// }
// return longest;